package com.binaryTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class BinaryTreeLevelOrderTraversal0206_102 {

//    // 迭代方式
//    public List<List<Integer>> levelOrder(TreeNode root) {
//        if(root == null) return new ArrayList<>();
//        List<List<Integer>> res = new ArrayList<>();
//        Queue<TreeNode> que = new LinkedList<>();
//        que.offer(root);
//
//        while (!que.isEmpty()){
//            List<Integer> itemList = new ArrayList<>();
//            int len = que.size();
//            while (len > 0){
//                TreeNode top = que.poll();
//                itemList.add(top.val);
//                if(top.left != null) que.offer(top.left);
//                if(top.right != null) que.offer(top.right);
//                len--;
//            }
//            res.add(itemList);
//        }
//        return res;
//    }

    //递归方式
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        checkFun(root,0);
        return res;
    }

    private void checkFun(TreeNode node, int deep) {
        if(node == null) return;
        deep++;

        if(res.size() < deep){      //当层级增加时，resList的Item也增加，利用resList的索引值进行层级界定
            List<Integer> item = new ArrayList<>();
            res.add(item);
        }
        res.get(deep-1).add(node.val);

        checkFun(node.left,deep);
        checkFun(node.right,deep);
    }
}
